Practice Problems (Week 7)

These practice problems (unlike the exercises) are not assessed. Use them to test your understanding, to challenge yourself, or whatever floats your boat.

1 The state monad

A very common pattern in functional programming is tail recursion. In a tail-recursive function, an extra argument (called the accumulator) is added to the function, where the result is accumulated. These two implementations of list reverse illustrate the point:

-- Not tail recursive
myReverse :: [a] -> [a]
myReverse [] = []
myReverse (x:xs) = xs ++ [x]

-- Tail recursive
myReverse' :: [a] -> [a]
myReverse' xs = myReverseAux xs [] where
  myReverseAux [] ys = ys
  myReverseAux (x:xs) ys = myReverseAux xs (x:ys)

The tail recursive style is more difficult to reason about. Usually, their main advantage is that they use less stack memory. In this case though, runtime improves too: myReverse xs is $O(|\mathit{xs}|^2)$ time, myReverse' xs is $O(|\mathit{xs}|)$ time. (Think about why that is).

Whenever we introduce auxiliary variables in this manner, we are in effect introducing background state into the computation. This means we could be using the state monad instead. Try it out by completing the following definition:

import Control.Monad.State

myReverse'' :: [a] -> [a]
myReverse'' xs = evalState (myReverseAux xs) [] where
  myReverseAux :: [a] -> State [a] [a]
  myReverseAux []     = undefined -- TODO
  myReverseAux (x:xs) =
    do
      modify undefined -- TODO
      myReverseAux xs

2 Monads done differently

An alternative but equivalent presentation of monads that you sometimes encounter is this:

class AltMonad m where
  returnA :: a -> m a
  joinA   :: m (m a) -> m a
  fmapA   :: (a -> b) -> m a -> m b

That is, instead of using return and >>= as our basic operations, we choose return, join and fmap.

Define an AltMonad instance on Maybe

instance AltMonad Maybe where
  -- returnA :: a -> Maybe a
  returnA = undefined --TODO
  -- joinA :: Maybe(Maybe a) -> Maybe a
  joinA   = undefined --TODO
  -- fmapA :: (a -> b) -> Maybe a -> Maybe b
  fmapA   = undefined --TODO

Define an AltMonad instance on lists.

instance AltMonad [] where
  -- returnA :: a -> [a]
  returnA = undefined --TODO
  -- joinA :: [[a]] -> [a]
  joinA   = undefined --TODO
  -- fmapA :: (a -> b) -> [a] -> [b]
  fmapA   = undefined --TODO

Show how the standard definition of monads follows from the alternative presentation by completing the following instance declaration.

{-# LANGUAGE FlexibleInstances, UndecidableInstances #-}
-- put the above line at the top of your file
instance Monad m => AltMonad m where
  returnA = return
  joinA   = undefined -- TODO
  fmapA   = undefined -- TODO

Show how the standard definition of monads can be obtained from the alternative presentation by completing the below instance declarations.

{-# LANGUAGE FlexibleInstances, UndecidableInstances #-}
-- put the above line at the top of your file
instance AltMonad m => Functor m where
  fmap = fmapA

instance AltMonad m => Applicative m where
  pure = returnA
  fm <*> xm = joinA $ fmapA (\x -> fmapA ($x) fm) xm

instance AltMonad m ==> Monad m  where
  returnA = return
  (>>=)   = undefined -- TODO

AltMonad also comes with laws. Here they are:

fmapA id m             == m
fmapA (f . g) m        == fmapA f (fmapA g m)
fmapA f (returnA x)    == returnA(f x)
fmapA f (joinA mm)     == joinA (fmapA (fmapA f) m)
joinA(returnA m)       == m
joinA(fmapA returnA m) == m
joinA(fmapA joinA mmm) == joinA(joinA mmm)

(At this point, the discerning reader may be able to guess why this presentation is less popular in computer science.) Given your definitions above, can you derive one set of laws from the other, and vice versa?

You may want to comment out the monad instances above once you're done playing with them. They're likely to confuse Haskell by introducing circularities into the type class resolution.

3 Applicatives

3.1 Zip-lists

The most common example of an Applicative instance that is not also a monad is the ZipList. The idea is that fs <*> xs applies the functions in fs elementwise to xs, like this: [f,g,h] <*> [x,y,z] == [f x, g y, h z]. If the lists have different length, the longer list gets truncated. We'll wrap this in a newtype to avoid clashing with the standard applicative instance for lists.

newtype MyZipList a = MyZipList [a] deriving (Eq,Show)

unZipList :: MyZipList a -> [a]
unZipList (MyZipList xs) = xs

instance Functor MyZipList where
  fmap f (MyZipList xs) = MyZipList $ fmap f xs

instance Applicative MyZipList where
  pure = MyZipList . repeat
  (<*>) = undefined --TODO

For lists, the definition of pure is much simpler: it creates a singleton list. Here we create an infinite list. Why?
Complete the definition of <*> in the code template above.
How is this definition of <*> different from the default Applicative instance on lists? Give an example.

3.2 Stream monads

We saw streams in the W5 practice problems. A stream is similar to a list, but because it has no base case, it cannot have finite length.

data Stream a = SCons a (Stream a)

instance Functor Stream where
  fmap f (SCons x xs) = SCons (f x) (fmap f xs)

{- This function returns the n:th element of a stream,
   or the 0:th if n is negative. It will come
   in handy later I promise!
 -}
nth :: Stream a -> Integer -> a
nth (SCons x xs) n
  | n <= 0    = x
  | otherwise = nth xs (n-1)

{- nats is the stream of all natural numbers:

     SCons 0 (Scons 1 (Scons 2 ...))

   It should obey this property:

     n >= 0   ==>  nth nats n = n
 -}
nats :: Stream Integer
nats = SCons 0 (succ <$> nats)

Streams admit a similar Applicative instance to ZipList. Define it.

instance Applicative Stream where
  pure = undefined --TODO
  (<*>) = undefined --TODO

We would like test whether we just defined a legal applicative instance or not. We can write a simple generator like this:
```
instance Arbitrary a => Arbitrary(Stream a) where
  arbitrary = SCons <$> arbitrary <*> arbitrary
```
…but there are no finite streams, so elementwise equality comparison is not guaranteed to terminate. If we're not careful, quickCheck will run forever. Fortunately, elementwise equality on streams obeys a property known as the take lemma, which states that two streams are equal iff all their same-length finite prefixes are equal.

How can you use this fact to devise an appropriate testing strategy for stream properties?
Despite being very similar to the non-monad MyZipList, Stream admits a lawful monad instance. Can you find it?

Hint: Stream a is isomorphic to functions from natural numbers to a. What is the monad definition for functions?
Why can't we use the idea from the previous question to define a monad for MyZipList along the same lines?